/* 
给出一个正整数，找出这个正整数所有数字全排列的下一个数。
说通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。让我们举几个例子。
如果输入12345，则返回12354。 如果输入12354，则返回12435。 如果输入12435，则返回12453。
*/

/* 
123652
1. 找到逆序区域的前一位，即3（652为逆序区）
2. 把逆序区域前一位，和逆序区域中大于它的最小的数字交换
3. 把原来的逆序区域变成顺序状态
*/

function findNearestNumber(numbers) {
    // find pivot
    let pivotIndex = 0;
    for (let i = numbers.length - 1; i > 0; i--) {
        if (numbers[i] > numbers[i - 1]) {
            pivotIndex = i - 1;
            break;
        }
    }
    // console.log(pivotIndex);

    if (pivotIndex === 0) return null;

    // exchange
    let min = numbers[pivotIndex];
    for (let i = numbers.length - 1; i > 0; i--) {
        if (numbers[i] > numbers[pivotIndex]) {
            numbers[pivotIndex] = numbers[i];
            numbers[i] = min;
            break;
        }
    }

    // reverse
    for (let i = pivotIndex + 1, j = numbers.length - 1; i < j; i++, j--) {
        const temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }

    return numbers;
}

const inputNumber = [1,2,3,6,5,2];
const res = findNearestNumber(inputNumber);
console.log(res);


// O(n)
// 字典序算法